package leetcode;

/**
 * @创建人 MBY381
 * @创建时间 2022/4/15 21:07
 * @描述 暂无
 */



public class Solution0142 {
    /**这个问题是需要数学转换的，具体的分析可以看上面的详细分析，这里面提一下大题的步骤。

     如果找到第一个交汇点，其中一个停止，另一个继续走，下一次交汇时候刚好走一圈，可以算出循环部分长度为y。

     所以我们知道的东西有：交汇时候fast走2x步，slow走x步，环长为y。并且快指针和慢指针交汇时候，
     多走的步数刚好是换长y的整数倍（它两此刻在同一个位置，快指针刚好多绕整数倍圈数才能在同一个位置相聚），
     可以得到2x=x+ny(x=ny)。其中所以说慢指针走的x和快指针多走的x是圈长y的整数倍。
     * 也就是说，从开头走到这个点共计x步，从这个点走x步也就是绕了几圈也回到这个点。
     * 如果说slow从起点出发，fast从这个点出发(每次走一步，相当于之前两步抵消slow走的路程)，
     * 那么走x步还会到达这个点，但是这两个指针这次都是每次走一步，所以一旦slow到达循环圈内，两个指针就开始汇合了。
     * @param args
     */
    public static void main(String[] args) {

    }

    public ListNode detectCycle(ListNode head) {
        boolean isloop=false;
        ListNode fast=new ListNode(0);//头指针
        ListNode slow=fast;
        fast.next=head;
        if(fast.next==null||fast.next.next==null)
            return null;
        while (fast!=null&&fast.next!=null) {
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow)
            {
                isloop=true;
                break;
            }
        }
        if(!isloop)//如果没有环返回
            return null;
        ListNode team=new ListNode(-1);//头指针 下一个才是head
        team.next=head;
        while (team!=fast) {//slow 和fast 分别从起点和当前点出发
            team=team.next;
            fast=fast.next;
        }
        return team;
    }


}